package day02;

/**
 * @author Jetwang
 * @version 1.0
 * @since 2023/3/2 20:14
 * 力扣 21
 */
public class LinkedListPractice07 {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return split(lists, 0 , lists.length - 1);
    }

    /**
     * 返回合并后的列表
     * @param lists
     * @param i
     * @param j
     * @return
     */
    private ListNode split(ListNode[] lists, int i, int j) {
        // 数组只剩一个链表
        if (i == j) {
            return lists[i];
        }
        int m = (i + j) >>> 1;
        ListNode left = split(lists, i , m);
        ListNode right = split(lists, m + 1 , j);
        return mergeTwoLists(left, right);
    }


    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}
